home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / sbprolog / amiga / v3_1 / sbp3_1e.lzh / ISORT.PL < prev    next >
Text File  |  1991-10-31  |  810b  |  37 lines
  1. /* From the book PROLOG PROGRAMMING IN DEPTH
  2.    by Michael A. Covington, Donald Nute, and Andre Vellino.
  3.    Copyright 1988 Scott, Foresman & Co.
  4.    Non-commercial distribution of this file is permitted. */
  5.  
  6. /* ISORT.PL */
  7. /* Insertion sort */
  8.  
  9.  
  10. /* To sort a list, sort its tail, then
  11.    insert its head in the right position. */
  12.  
  13. isort([Head|Tail],Result) :-
  14.     !,
  15.     isort(Tail,SortedTail),
  16.     insert(Head,SortedTail,Result).
  17.  
  18. isort([],[]).
  19.  
  20.  
  21. /* To insert an item into the correct position
  22.    in a sorted list: Put it at the beginning
  23.    if it should precede the first element;
  24.    otherwise CDR down the list until a position
  25.    is found where this is the case. */
  26.  
  27. insert(X,[Y|Tail],[X,Y|Tail]) :-
  28.     X =< Y,
  29.     !.
  30.  
  31. insert(X,[Y|Tail],[Y|Z]) :-
  32.     X > Y,
  33.     !,
  34.     insert(X,Tail,Z).
  35.  
  36. insert(X,[],[X]).
  37.